#define N 100002
bool isEvenOddTree(struct TreeNode* root){
    struct TreeNode *queue[N];
    int front = 0;
    int rear = 0;
    int odd = 0;
    int pre;

    queue[rear++] = root;
    while(front != rear) {
        int cnt = rear - front;
        if (odd == 1) pre = INT_MAX;
        if (odd == 0) pre = INT_MIN;
        for (int i = 0; i < cnt; i++) {
            root = queue[front++];
            if ((odd == 1) && (root->val % 2 != 0 || pre <= root->val)) return false;
            if ((odd == 0) && (root->val % 2 != 1 || pre >= root->val)) return false;

            pre = root->val;
            if (root->left) queue[rear++] = root->left;
            if (root->right) queue[rear++] = root->right;
        }
        odd = (odd + 1) % 2;
    }

    return true;
}
